/*
 * @lc app=leetcode.cn id=15 lang=javascript
 *
 * [15] 三数之和
 */

// @lc code=start
/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var threeSum = function (nums) {
  nums.sort((a, b) => a - b);
  const n = nums.length;
  const res = [];
  // 先固定第一个元素
  for (let k = 0; k < n - 2; k++) {
    let target = 0 - nums[k];
    // 避免第一个元素重复
    if (k > 0 && nums[k - 1] === nums[k]) continue;
    let i = k + 1;
    let j = n - 1;
    let sum;
    while (i < j) {
      sum = nums[i] + nums[j];
      if (sum === target) {
        res.push([nums[i], nums[j], nums[k]]);

        // 避免第二三个元素重复
        while (i < j && nums[i] === nums[i + 1]) i++;
        while (i < j && nums[j - 1] === nums[j]) j--;
      }
      if (sum > target) {
        j--;
      } else {
        i++;
      }
    }
  }
  return res;
};
// @lc code=end
